/**
 * Project Name:JavaBaseReview
 * Package Name:com.xuwei.base.tree
 * author:David
 * Date:2016年5月9日上午8:38:08
 * Copyright (c) 2016, xw123box@126.com All Rights Reserved.
 *
 */
package com.xuwei.base.tree;

import com.xuwei.base.link.Iterator;
import com.xuwei.base.link.LinkedList;
import com.xuwei.base.link.LinkedListDLNode;
import com.xuwei.base.queue.Queue;
import com.xuwei.base.queue.QueueArray;
import com.xuwei.base.stack.Stack;
import com.xuwei.base.stack.StackSLinked;

/**
 * 基于BinTreeNode实现的二叉树
 * @author David
 * @since 2016年5月9日 上午8:38:08
 * @version 
 * @since JDK 1.6
 */
public class BinaryTreeLinked {
	private BinTreeNode root;
	
	//先序遍历二叉树
	public Iterator preOrder(){
		LinkedList list = new LinkedListDLNode();
		preOrderRecursion(this.root, list);
		return list.elements();
	}
	
	//先序遍历的递归算法
	private void preOrderRecursion(BinTreeNode rt, LinkedList list) {
		if(rt==null)return;//递归基，空树直接返回
		list.insertLast(rt);//访问根结点
		preOrderRecursion(rt.getLChild(), list);//遍历左子树
		preOrderRecursion(rt.getRChild(), list);//遍历右子树
	}

	//先序遍历二叉树
	public Iterator preOrder2(){
		LinkedList list = new LinkedListDLNode();
		preOrderTraverse(this.root,list);
        return list.elements();				
	}
	
	//先序遍历的非递归算法
	private void preOrderTraverse(BinTreeNode rt, LinkedList list) {
		if(rt==null)return;
		BinTreeNode p = rt;
		Stack s = new StackSLinked();
		while(p!=null){
			while(p!=null){ //向左走到尽头
				list.insertLast(p);//访问根
				if(p.hasRChild()){
					s.push(p.getRChild());//右子树根结点入栈
				}
				p = p.getLChild();
			}
			if(!s.isEmpty()){
				p = (BinTreeNode) s.pop();//右子树根退栈遍历右子树
			}
		}
	}

	//中序遍历二叉树
	public Iterator inOrder(){
		LinkedList list = new LinkedListDLNode();
		inOrderTraverse(this.root,list);
		return list.elements();
	}
	
	//中序遍历的非递归算法
	private void inOrderTraverse(BinTreeNode rt, LinkedList list){
		if(rt==null)return;
		BinTreeNode p = rt;
		Stack s = new StackSLinked();
		while(p!=null||!s.isEmpty()){
			while(p!=null){//一直向左走
				s.push(p); //将根结点入栈
				p = p.getLChild();
			}
			if(!s.isEmpty()){
				p = (BinTreeNode)s.pop();//取出栈顶根结点访问之
				list.insertLast(p);
				p = p.getRChild();//转向根的右子树进行遍历
			}
		}
	}
	
	//后序遍历二叉树
	public Iterator postOrder(){
		LinkedList list = new LinkedListDLNode();
		postOrderTraverse(this.root,list);
		return list.elements();
	}
	
	//后序遍历的非递归算法
	private void postOrderTraverse(BinTreeNode rt, LinkedList list){
		if(rt==null)return;
		BinTreeNode p = rt;
		Stack s = new StackSLinked();
		while(p!=null||!s.isEmpty()){
			while(p!=null){   //先左后右不断深入
				s.push(p);    //将根结点入栈
				if(p.hasLChild()){
					p = p.getLChild();
				}else{
					p = p.getRChild();
				}
			}
			if(!s.isEmpty()){
				p = (BinTreeNode)s.pop();//取出栈顶根结点访问之
				list.insertLast(p);
			}
			//满足条件时，说明栈顶根结点右子树已访问，应出栈访问之
			while(!s.isEmpty()&&((BinTreeNode)s.peek()).getRChild()==p){
				p = (BinTreeNode)s.pop();
				list.insertLast(p);
			}
			//转向栈顶根结点的右子树继续后序遍历
			if(!s.isEmpty()){
				p = ((BinTreeNode)s.peek()).getRChild();
			}else{
				p = null;
			}
		}
	}
	
	//按层遍历二叉树
	public Iterator levelOrder(){
		LinkedList list = new LinkedListDLNode();
		levelOrderTraverse(this.root,list);
		return list.elements();
	}
	
	//使用队列完成二叉树的按层遍历
	private void levelOrderTraverse(BinTreeNode rt, LinkedList list) {
		if(rt==null)return;
		Queue q = new QueueArray();
		q.enqueue(rt);   //根结点入队
		while(!q.isEmpty()){
			BinTreeNode p = (BinTreeNode) q.dequeue();//取出队首结点p并访问
			list.insertLast(p);
			if(p.hasLChild()){
				q.enqueue(p.getLChild());//将p的非空左右子树依次入队
			}
			if(p.hasRChild()){
				q.enqueue(p.getRChild());
			}
		}
	}

	//在树中查找元素e，返回其所在结点
	public BinTreeNode find(Object e){
		return searchE(root, e);
	}
	
	//递归查找元素e
	private BinTreeNode searchE(BinTreeNode rt, Object e) {
		if(rt==null)return null;
		if(e==rt)return rt;//如果是根结点，返回根
		BinTreeNode v = searchE(rt.getLChild(), e);//否则在左子树中找
		if(v==null){
			v = searchE(rt.getRChild(), e);//没找到，在右子树中找
		}
		return v;
	}

	public BinTreeNode getRoot() {
		return root;
	}

	public void setRoot(BinTreeNode root) {
		this.root = root;
	}
	
}
